A kd-tree(short for k-dimensional tree) is a well-known space-partitioning data structure for organizing points in k-dimensional space. As an acceleration structure, kd-trees have been used in a variety of graphics applications.
Because of its significant usage in graphics, fast kd-tree construction has been a subject of much interest in recent years, with several CPU-based algorithms proposed and/or implemented. However, real-time construction of kd-trees on the GPU was heretofore an unsolved problem.